package leetcode; /**
 * description:
 * author:张腾
 * date:2021-06-13
 */

import java.util.ArrayDeque;
import java.util.LinkedList;

/**
 * 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
 *
 * 给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
 */
public class leetcode331 {
    //用”#“标识空节点，当遇到两个#就是当前节点为叶子节点，将该节点转换为#即可，递归向上转换
    public boolean isValidSerialization(String preorder) {
        LinkedList<String> stack = new LinkedList<>();
        for (String s : preorder.split(",")) {
            stack.push(s);
            while (stack.size()>=3 && stack.get(0).equals("#")
                    && stack.get(1).equals("#") && !stack.get(2).equals("#")){
                stack.pop();
                stack.pop();
                stack.pop();
                stack.push("#");
            }
        }
        return stack.size()==1 && stack.pop().equals("#");
    }
}
